//
// Created by Administrator on 2021/5/28.
//
#include <iostream>
#include <vector>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *convertBST(TreeNode *root) {
        // 用一个变量储存遍历过程的和
        // 右 中 左 的顺序进行遍历
        int acc = 0;
        dfs(root, acc);
        return root;
    }

    void dfs(TreeNode *root, int &accumulate) {
        if (root == nullptr) return;
        dfs(root->right, accumulate);
        accumulate += root->val;
        root->val = accumulate;
        dfs(root->left, accumulate);
    }

    void inorder(TreeNode *t, vector<int> &v) { // 递归函数
        if (t == nullptr) {
            return;
        }
        inorder(t->left, v);
        v.push_back(t->val);
        inorder(t->right, v);
    }

    vector<int> inorderTraversal(TreeNode *root) { // 递归解法
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
};

class Solution2 { // 题解
public:
    int sum = 0;

    TreeNode *convertBST(TreeNode *root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};


int main() {
    auto n1 = TreeNode(4), n2 = TreeNode(1), n3 = TreeNode(6), n4 = TreeNode(0),
            n5 = TreeNode(2), n6 = TreeNode(5), n7 = TreeNode(7), n8 = TreeNode(3),
            n9 = TreeNode(8);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;
    n3.right = &n7;
    n5.right = &n8;
    n7.right = &n9;
    Solution sol;
    auto ans = sol.convertBST(&n1);
    auto v = sol.inorderTraversal(ans);
    for (auto &x:v) cout << x << endl;
    return 0;
}